import java.util.HashSet;
import java.util.List;

class Solution1 {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        for(int i = 1; i<=n; i++) {
            if(nums[i-1] > 0) {
                f[i] = f[i-1] + 1;
                g[i] = g[i] == 0 ? 0 : g[i-1] + 1;
            }else {
                f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
                g[i] = f[i-1] + 1;
            }
        }
        int ret = f[1];
        for(int i = 1; i<=n;i++) {
            ret = Math.max(ret,f[i]);
        }
        return ret;
    }
}

class Solution2 {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        int ret = 0;
        for(int i = 2; i<n; i++) {
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-1]) {
                dp[i] = dp[i-1] + 1;
            }
            ret += dp[i];
        }
        return ret;
    }
}

class Solution3 {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0; i<n; i++) {
            f[i] = g[i] = 1;
        }
        int ret = 1;
        for(int i = 1; i<n; i++) {
            if(arr[i-1] < arr[i]) {
                f[i] = g[i-1] + 1;
            }else if(arr[i-1] > arr[i]) {
                g[i] = f[i-1] + 1;
            }
            ret = Math.max(ret,Math.max(f[i],g[i]));
        }
        return ret;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        for(String str : wordDict) {
            set.add(str);
        }
        int n = s.length();
        s = " " + s;
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for(int i = 1; i<=n; i++) {
            for(int j = i; j>=1; j--) {
                if(dp[j-1] && set.contains(s.substring(j,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}












public class Test {
}
